package com.myself.module.source.sort;

import java.util.Arrays;

/**
 * @author 瑟瑟发抖
 * @version 1.0
 * @description 合并排序
 * @date 2024/4/12 18:00
 */

public class MergeSort {

    private static int[] ints;

    public static void sort(int[] input) {
        ints = new int[input.length];
        sort(input, 0, input.length - 1);
    }

    public static void sort(int[] input, int smallIndex, int bigIndex) {
        if (bigIndex <= smallIndex) {
            return;
        }
        int mid = smallIndex + (bigIndex - smallIndex) / 2;
        sort(input, smallIndex, mid);//左
        sort(input, mid + 1, bigIndex);//右
        merge(input, smallIndex, mid, bigIndex);

    }

    public static void merge(int[] a, int low, int mid, int high) {

        int[] aux = new int[a.length];
        int i = low, j = mid + 1;
        //将原数组复制到临时数组中
        for(int k = low; k <= high; k++){
            aux[k] = a[k];
        }

        for(int k=low;k<=high;k++){
            if(i > mid) a[k] = aux[j++];              //左半边用尽(开始用到右半边)
            else if(j > high) a[k] = aux[i++];        //右半边用尽
            else if(aux[j] < aux[i]) a[k] = aux[j++]; //右半边的当前元素小于左半边的当前元素
            else a[k] = aux[i++];                     //左半边的当前元素大于右半边的当前元素
        }
    }


    public static void main(String[] args) {
        int[] ints = {1, 8, 9, 5, 4, 100, 11, 12};
        sort(ints);
        System.out.println(Arrays.toString(ints));
    }
}
